#include<bits/stdc++.h>
using namespace std;
int dp[800][800]{};
int main(){
//	1
//	wwrcrcww

    int T;
    cin>>T;
    string s;
    int length;
    while(T--){
        cin>>s;
        length=s.size();
        int len=2;
        for(len=1;len<=length;len++){
            for(int l=0;l<=length-len;++l){
                int r=l+len-1;
                if(l==r){
                    dp[l][r]=1;
                    continue;
                }
                dp[l][r]=INT_MAX;
                if(s[l]==s[r]){
                    if(l+1==r) dp[l][r]=dp[l+1][r];
                    else dp[l][r]=dp[l+1][r-1];
                }else{
                    for(int k=l;k<r;k++)
                        dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
                }
            }
        }
        cout<<dp[0][length-1]<<endl;
    }

    return 0;
}
